home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource4 / 244_01 / one41.c < prev    next >
Text File  |  1987-10-26  |  6KB  |  233 lines
  1.  
  2. /* program to analyze the de Bruijn diagram of a cellular */
  3. /* automaton and report all the periodic states. */
  4. /* states with period 1 and displacements zero (1,0) or one (1,1) */
  5. /* are analyzed for a four-state, nearest neighbor (4,1) automaton */
  6. /* [Harold V. McIntosh, 4 May 1987] */
  7.  
  8. # include <stdio.h>
  9.  
  10. # define MC     9                /* maximum number of columns */
  11. # define NS     10                /* number of distinct sums */
  12. # define NW    24                /* pause after so many lines */
  13.  
  14. char arry[4][4][4];
  15. int  rule[NS];
  16. int  nc, nl;
  17.  
  18. main() {char c; int i;
  19.  
  20. printf("Rule number:\n\n");
  21. printf("0..1..2..3\n");
  22. for (i=0; i<NS; i++) rule[i]=getchar()-'0';
  23.  
  24. nc=0;
  25. nl=0;
  26.  
  27. do {
  28. printf("  a=still  b=glider  0,1,2,3=constant  q=quit\015");
  29. c=kbdin();
  30. switch (c) {
  31. case 'a':
  32. printf("Sequences satisfying the condition (1,0):       "); kwait(0);
  33. pass1a(); pass2i(); pass2o(); pass4(); break;
  34. case 'b':
  35. printf("Sequences satisfying the condition (1,1):       "); kwait(0);
  36. pass1b(); pass2i(); pass2o(); pass4(); break;
  37. case '0':
  38. printf("Sequences mapping into a constant string of 0's:"); kwait(0);
  39. pass1x(0); pass2i(); pass2o(); pass4(); break;
  40. case '1':
  41. printf("Sequences mapping into a constant string of 1's:"); kwait(0);
  42. pass1x(1); pass2i(); pass2o(); pass4(); break;
  43. case '2':
  44. printf("Sequences mapping into a constant string of 2's:"); kwait(0);
  45. pass1x(2); pass2i(); pass2o(); pass4(); break;
  46. case '3':
  47. printf("Sequences mapping into a constant string of 3's:"); kwait(0);
  48. pass1x(3); pass2i(); pass2o(); pass4(); break;
  49. default: break; };
  50.  } while (c!='q');
  51.  
  52. } /* end main */
  53.  
  54. /* Pass 1a marks all the configurations which fulfil (1,0) */
  55. pass1a() {int i,j,k;
  56.   printf(" Pass1a\015");
  57.   for (i=0; i<4; i++) {
  58.   for (j=0; j<4; j++) {
  59.   for (k=0; k<4; k++) {
  60.   arry[i][j][k]=rule[i+j+k]==j?'Y':'N';
  61.   };};}; }
  62.  
  63. /* Pass 1b marks all the configurations which fulfil (1,1) */
  64. pass1b() {int i,j,k;
  65.   printf(" Pass1b\015");
  66.   for (i=0; i<4; i++) {
  67.   for (j=0; j<4; j++) {
  68.   for (k=0; k<4; k++) {
  69.   arry[i][j][k]=rule[i+j+k]==i?'Y':'N';
  70.   };};}; }
  71.  
  72. /* Pass 1x marks all the configurations mapping into a constant */
  73. pass1x(c) int c; {int i,j,k;
  74.   printf(" Pass1a\015");
  75.   for (i=0; i<4; i++) {
  76.   for (j=0; j<4; j++) {
  77.   for (k=0; k<4; k++) {
  78.   arry[i][j][k]=rule[i+j+k]==c?'Y':'N';
  79.   };};}; }
  80.  
  81. /* Pass 2i flags all links with an incoming arrow */
  82. /* Pass 2o flags all links with an outgoing arrow */
  83. /* Then pass 3 discards all unflagged links */
  84. /* Passes 2 and 3 alternate until no change is observed */
  85.  
  86. pass2i() {int i, j, k, m;
  87. do {
  88. printf(" Pass2i\015");
  89. for (i=0; i<4; i++) {
  90. for (j=0; j<4; j++) {
  91. for (k=0; k<4; k++) {
  92. if ((arry[i][j][k]&0x5F)=='Y') {for (m=0; m<4; m++) arry[j][k][m]|=0x20;};
  93. };};}; } while (pass3()!=0); }
  94.  
  95. pass2o() {int i, j, k, m;
  96. do {
  97. printf(" Pass2o\015");
  98. for (i=0; i<4; i++) {
  99. for (j=0; j<4; j++) {
  100. for (k=0; k<4; k++) {
  101. if ((arry[i][j][k]&0x5F)=='Y') {for (m=0; m<4; m++) arry[m][i][j]|=0x20;};
  102. };};} } while (pass3()!=0); }
  103.  
  104. /* Pass 3 - erase flags, mark survivors, count changes */
  105.  
  106. int pass3() {int i, j, k, l;
  107. l=0;
  108. printf(" Pass3\015");
  109. for (i=0; i<4; i++) {
  110. for (j=0; j<4; j++) {
  111. for (k=0; k<4; k++) {
  112.   switch (arry[i][j][k]) {
  113.     case 'y': arry[i][j][k]='Y'; break;
  114.     case 'Y': arry[i][j][k]='N'; l=1; break;
  115.     case 'n': case 'N': arry[i][j][k]='N'; break;
  116.     default: break; };
  117. };};};
  118. return l;
  119. }
  120.  
  121. /* pass4 - print loops which remain */
  122. pass4() {
  123. int i0, i1, i2;
  124. int j0, j1, j2, k, l, m;
  125. printf(" pass4 \015");
  126. for (i0=0; i0<4; i0++) {
  127. for (i1=0; i1<4; i1++) {
  128. for (i2=0; i2<4; i2++) {
  129. j1=i1; j2=i2;l=0; m=0;
  130. do {
  131.         if (arry[0][j1][j2]=='Y')
  132.     {arry[0][j1][j2]='y';
  133.     k=j2; j2=j1; j1=0; m=1;}
  134.   else {if (arry[1][j1][j2]=='Y')
  135.     {arry[1][j1][j2]='y';
  136.     k=j2; j2=j1; j1=1; m=1;}
  137.   else {if (arry[2][j1][j2]=='Y')
  138.     {arry[2][j1][j2]='y';
  139.     k=j2; j2=j1; j1=2; m=1;}
  140.   else {if (arry[3][j1][j2]=='Y')
  141.     {arry[3][j1][j2]='y';
  142.     k=j2; j2=j1; j1=3; m=1;}
  143.   else {l=1; if (m==1) {j0=j1; j1=j2; j2=k;}; };};};};
  144.   } while (l==0);
  145. l=0; 
  146. m=0;
  147. do {
  148.         if (arry[j0][j1][0]=='y')
  149.    {prf(j0,j1,0);
  150.    arry[j0][j1][0]='N';
  151.    j0=j1; j1=0; m=1;}
  152.   else {if (arry[j0][j1][1]=='y')
  153.    {prf(j0,j1,1);
  154.    arry[j0][j1][1]='N';
  155.    j0=j1; j1=1; m=1;}
  156.   else {if (arry[j0][j1][2]=='y')
  157.    {prf(j0,j1,2);
  158.    arry[j0][j1][2]='N';
  159.    j0=j1; j1=2; m=1;}
  160.   else {if (arry[j0][j1][3]=='y')
  161.    {prf(j0,j1,3);
  162.    arry[j0][j1][3]='N';
  163.    j0=j1; j1=3; m=1;}
  164.   else {l=1;};};};};
  165.   } while (l==0);
  166. l=0;
  167. do {
  168.         if (arry[j0][j1][0]=='Y')
  169.    {prf(j0,j1,0);
  170.    arry[j0][j1][0]='N';
  171.    j0=j1; j1=0; m=1;}
  172.   else {if (arry[j0][j1][1]=='Y')
  173.    {prf(j0,j1,1);
  174.    arry[j0][j1][1]='N';
  175.    j0=j1; j1=1; m=1;}
  176.   else {if (arry[j0][j1][2]=='Y')
  177.    {prf(j0,j1,2);
  178.    arry[j0][j1][2]='N';
  179.    j0=j1; j1=2; m=1;}
  180.   else {if (arry[j0][j1][3]=='Y')
  181.    {prf(j0,j1,3);
  182.    arry[j0][j1][3]='N';
  183.    j0=j1; j1=3; m=1;}
  184.   else {l=1; if (m==1) kwait(0);};};};};
  185.   } while (l==0);
  186. };};};
  187. }
  188.  
  189. /* print one link of the de Bruijn diagram */
  190. prf(i,j,k) int i, j, k; {
  191. kwait(1);
  192. printf("%1d",i);
  193. printf("%1d",j);
  194. printf("-");
  195. printf("%1d",k);
  196. printf("  ");}
  197.  
  198. /* print the whole array */
  199. /* mostly for debugging */
  200. pall() {int i, j, k;
  201. for (i=0; i<4; i++) {
  202. for (j=0; j<4; j++) {
  203. for (k=0; k<4; k++) {
  204. printf("%c",arry[i][j][k]);
  205. };};};
  206. printf("\n");
  207. }
  208.  
  209. /* keyboard status */
  210. kbdst() {return bdos(11)&0xFF;}
  211.  
  212. /* direct keyboard input, no echo */
  213. kbdin() {int c;
  214. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  215. return c;}
  216.  
  217. /* pause at the end of a full screen */
  218. kwait(i) int i; {
  219. switch (i) {
  220.   case 0: printf("\n"); nc=0; nl++; break;
  221.   case 1: if (nc==MC) {printf("&\n"); nc=1; nl++;} else nc++; break;
  222.   default: break;};
  223. if (nl==NW) {
  224.   nl=0;
  225.   printf(" press any key to continue\015");
  226.   while (kbdst()) {};
  227.   kbdin();
  228.   printf("-                         \n");
  229.   };
  230. }
  231.  
  232. /* end */
  233.